HackerRank The Maximum Subarray

https://www.hackerrank.com/challenges/maxsubarray/problem

提出

code: python

#!/bin/python3

import math

import os

import random

import re

import sys

# Complete the 'maxSubarray' function below.

# The function is expected to return an INTEGER_ARRAY.

# The function accepts INTEGER_ARRAY arr as parameter.

def maxSubarray(arr):

# Write your code here

subsequence = 0

for i in arr:

if i > 0:

subsequence += i

if subsequence == 0:

subsequence += max(arr)

cumu = [arr0]

for i in range(1, len(arr)):

cumu.append(arri + cumu-1)

print(cumu)

return subsequence

if __name__ == '__main__':

fptr = open(os.environ'OUTPUT_PATH', 'w')

t = int(input().strip())

for t_itr in range(t):

n = int(input().strip())

arr = list(map(int, input().rstrip().split()))

result = maxSubarray(arr)

fptr.write(' '.join(map(str, result)))

fptr.write('\n')

fptr.close()

解答

code: python

#!/bin/python3

import math

import os

import random

import re

import sys

# Complete the 'maxSubarray' function below.

# The function is expected to return an INTEGER_ARRAY.

# The function accepts INTEGER_ARRAY arr as parameter.

'''

-2,3,2,-1,5,100,-50,130,-90

-2 3 5 4 9 109 59 189 99

-2 3 5 5 9 109 109 189 189

'''

def maxSubarray(arr):

# Write your code here

subsequence = 0

for i in arr:

if i > 0:

subsequence += i

if subsequence == 0:

subsequence += max(arr)

# Kadane's Algorithm

max_current = max_global = arr0

for i in range(1, len(arr)):

max_current = max(arri, max_current + arri)

max_global = max(max_global, max_current)

return max_global, subsequence

if __name__ == '__main__':

fptr = open(os.environ'OUTPUT_PATH', 'w')

t = int(input().strip())

for t_itr in range(t):

n = int(input().strip())

arr = list(map(int, input().rstrip().split()))

result = maxSubarray(arr)

fptr.write(' '.join(map(str, result)))

fptr.write('\n')

fptr.close()

メモ

https://www.youtube.com/watch?v=86CQq3pKSUw

https://scrapbox.io/files/61d256f628f4e700218b31cb.png

提出

code: python

#!/bin/python3

import math

import os

import random

import re

import sys

# Complete the 'maxSubarray' function below.

# The function is expected to return an INTEGER_ARRAY.

# The function accepts INTEGER_ARRAY arr as parameter.

def maxSubarray(arr):

# Write your code here

suba = 0

subs = 0

for i in arr:

if i > 0:

subs += i

return suba, subs if subs > 0 else max(arr)

if __name__ == '__main__':

fptr = open(os.environ'OUTPUT_PATH', 'w')

t = int(input().strip())

for t_itr in range(t):

n = int(input().strip())

arr = list(map(int, input().rstrip().split()))

result = maxSubarray(arr)

fptr.write(' '.join(map(str, result)))

fptr.write('\n')

fptr.close()

提出

code: python

#!/bin/python3

import math

import os

import random

import re

import sys

# Complete the 'maxSubarray' function below.

# The function is expected to return an INTEGER_ARRAY.

# The function accepts INTEGER_ARRAY arr as parameter.

'''

1 2 3 4

2 -1 2 3 4 -5

subarray sums

2, 1, 3, 6, 10, 5

-> 10

-2 -3 -1 -4 -6

-2, -5, -6, -10, -16

-> -2 incorrect

dp i

subsequence sums

if v > 0: res += v

'''

def maxSubarray(arr):

# Write your code here

if __name__ == '__main__':

fptr = open(os.environ'OUTPUT_PATH', 'w')

t = int(input().strip())

for t_itr in range(t):

n = int(input().strip())

arr = list(map(int, input().rstrip().split()))

result = maxSubarray(arr)

fptr.write(' '.join(map(str, result)))

fptr.write('\n')

fptr.close()